package com.cat.dataStructure03;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-xor-sum-of-two-arrays/
 * @create 2025/11/15 19:47
 * @since JDK17
 */

public class Solution61 {
    int[] nums1, nums2;
    int[][] dp;
    int n;
    int f(int i, int status) {
        if (i == n) {
            return 0;
        }
        if (dp[i][status] != -1) {
            return dp[i][status];
        }
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            if (((status >> j) & 1) == 0) { // 还没有用过
                ans = Math.min(ans, (nums2[j] ^ nums1[i]) + f(i + 1, status | (1 << j)));
            }
        }

        return dp[i][status] = ans;
    }
    public int minimumXORSum(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        n = nums1.length;
        dp = new int[n][1 << n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }

        return f(0, 0);
    }
}
